home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 140 / Gekkan Dennou Club - 2000.1 Vol. 140 (Japan) (Track 1).bin / docs / perl / eight.c next >
Encoding:
C/C++ Source or Header  |  1999-10-29  |  3.9 KB  |  190 lines
  1. /*
  2.  * eight.c : ８パズルの解法（メモリは約 5 M Byte 必要）
  3.  *
  4.  *           Copyright (C) 1999 by Makoto Hiroi
  5.  *
  6.  * 座標     完成形
  7.  *  0 1 2   1 2 3
  8.  *  3 4 5   4 5 6
  9.  *  6 7 8   7 8 0  : 0 は空白を表す
  10.  */
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include <ctype.h>
  15. #include <time.h>
  16.  
  17. /* 状態数 (9! / 2) */
  18. #define S_SIZE 181440
  19. #define B_SIZE 9
  20. #define MAX_MOVE 31
  21.  
  22. #define TRUE  1
  23. #define FALSE 0
  24.  
  25. /* 状態（二分木を構成する） */
  26. typedef struct {
  27.   char  board[B_SIZE];
  28.   short zp;             /* 0 の位置 */
  29.   int   prev;
  30.   int   right;
  31.   int   left;
  32. } State;
  33.  
  34. /* 状態数を格納するテーブル(約 4.4 M byte) */
  35. State state_table[S_SIZE];
  36.  
  37. /* n 手目が始まるステート番号を記憶 */
  38. int move_table[MAX_MOVE + 1];
  39.  
  40. /* 隣接リスト */
  41. short adjacent[9][5] = {
  42.   1, 3,-1,-1,-1,
  43.   0, 4, 2,-1,-1,
  44.   1, 5,-1,-1,-1,
  45.   0, 4, 6,-1,-1,
  46.   1, 3, 5, 7,-1,
  47.   2, 4, 8,-1,-1,
  48.   3, 7,-1,-1,-1,
  49.   4, 6, 8,-1,-1,
  50.   5, 7,-1,-1,-1,
  51. };
  52.  
  53. /* 終了状態 */
  54. char end_state[B_SIZE] = {1,2,3,4,5,6,7,8,0};
  55.  
  56. /* 追加する */
  57. int insert_tree( int i )
  58. {
  59.   int n = 0;
  60.   while( 1 ){
  61.     int next;
  62.     int r = memcmp( state_table[i].board, state_table[n].board, B_SIZE );
  63.     if( r == 0 ){
  64.       /* 登録済み */
  65.       return FALSE;
  66.     } else if( r < 0 ){
  67.       /* 左へたどる */
  68.       if( (next = state_table[n].left) == -1 ){
  69.     state_table[n].left = i;
  70.     return TRUE;
  71.       }
  72.     } else {
  73.       /* 右へたどる */
  74.       if( (next = state_table[n].right) == -1 ){
  75.     state_table[n].right = i;
  76.     return TRUE;
  77.       }
  78.     }
  79.     n = next;
  80.   }
  81. }
  82.  
  83. /* 初期化 */
  84. void init( char *init_state )
  85. {
  86.   int  i = 0;
  87.   char *ptr = state_table[0].board;
  88.   for( ; i < B_SIZE; i++ ){
  89.     if( (*ptr++ = *init_state++) == 0 ){
  90.       state_table[0].zp = i;
  91.     }
  92.   }
  93.   state_table[0].prev  = -1;
  94.   state_table[0].left  = -1;
  95.   state_table[0].right = -1;
  96.   move_table[0] = 0;
  97. }  
  98.  
  99. /* 盤面を表示する */
  100. void print_board( char *b )
  101. {
  102.   int i;
  103.   for( i = 0; i < B_SIZE; i++ ){
  104.     printf("%d ", b[i] );
  105.     if( i == 2 || i == 5 ) printf("\n");
  106.   }
  107.   printf("\n\n");
  108. }
  109.  
  110. /* 手順を表示 */
  111. void print_history( int num )
  112. {
  113.   print_board( end_state );
  114.   while( num != -1 ){
  115.     print_board( state_table[num].board );
  116.     num = state_table[num].prev;
  117.   }
  118. }
  119.  
  120. /* 探索関数 */
  121. int search( char *init_state )
  122. {
  123.   int move = 1, count = 1;
  124.   init( init_state ); 
  125.   while( count > move_table[move - 1] ){
  126.     int i = move_table[move - 1];
  127.     printf("%d 手の検索：局面数 %d 個\n", move, count ); fflush( stdout );
  128.     move_table[move] = count;
  129.     for( ; i < move_table[move]; i++ ){
  130.       short  zp = state_table[i].zp;
  131.       char   *b = state_table[i].board;
  132.       short  *p = adjacent[zp];
  133.       for( ; *p != -1; p++ ){
  134.     /* 盤面をコピー */
  135.     char *b1 = state_table[count].board;
  136.     memcpy( b1, b, B_SIZE );
  137.     /* 駒の移動 */
  138.     b1[zp] = b1[*p];
  139.     b1[*p] = 0;
  140.  
  141.     if( !memcmp( end_state, b1, B_SIZE ) ){
  142.       /* 解けた */
  143.           print_history( i );
  144.       return TRUE;
  145.     } else if( insert_tree( count ) ){
  146.       /* 二分木に追加できたので同じ状態はない */
  147.       state_table[count].zp    = *p;
  148.       state_table[count].prev  = i;
  149.       state_table[count].left  = -1;
  150.       state_table[count++].right = -1;
  151.     }
  152.       }
  153.     }
  154.     /* 次の移動 */
  155.     move++;
  156.   }
  157.   return FALSE;
  158. }
  159.  
  160. volatile void usage( void )
  161. {
  162.   fprintf( stderr, "usage : eight state\n state は 0 - 8 の数字を一つずつ ex 123456708\n" );
  163.   exit( 1 );
  164. }
  165.  
  166. int main( int argc, char *argv[] )
  167. {
  168.   int i, start;
  169.   char init_state[B_SIZE];
  170.   if( argc != 2 ){
  171.     usage();
  172.   }
  173.   /* 初期の配置を取得 */
  174.   for( i = 0; i <  B_SIZE; i++ ){
  175.     int n = argv[1][i];
  176.     if( !isdigit( n ) || n == '9' ) usage();
  177.     n = n - '0';
  178.     if( i > 0 && memchr( init_state, n, i ) != NULL ) usage();  /* 同じ数字が使われている */
  179.     init_state[i] = n;
  180.   }
  181.   /* 検索開始 */
  182.   start = clock();
  183.   search( init_state );
  184.   printf("時間 %d\n", clock() - start );
  185.   return 0;
  186. }
  187.  
  188. /* end of file */
  189.  
  190.